/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package bst;

/**
 *
 * @author mweya
 */
public class Tree {
    public Node rootNoRecursion = null;
    //public Node recursiveRoot = null;
    
    public Tree() {}
    
    public Tree(int toadd) {
        add(toadd);
    }
    
    /* Broken, might fix later
    
    public void delete(int key) {
        Node cursor = search(key);
        // Case one, no witnesses
        if (cursor.getLeft() == null && cursor.getRight() == null) {
            cursor = null;
        } 
        // Case two, one witness
        if (cursor.getLeft() == null && cursor.getRight() != null) {
            cursor = cursor.getRight();
        }
        if (cursor.getRight() == null && cursor.getLeft() != null) {
            cursor = cursor.getLeft();
        }
        // Worst case
        if (cursor.getRight() != null && cursor.getLeft() != null) {
            Node tempRight= search(key).getRight();
            Node tempLeft = search(key).getLeft();
            
            cursor = cursor.getLeft();
            while (cursor.getRight() != null) {
                cursor = cursor.getRight();
            }
            
            cursor.setRight(tempRight);
            cursor.setLeft(tempLeft);
            
            rootNoRecursion = cursor;
            
        }
    }*/
    
    
    // Thanks Geeks for Geeks
    public void deleteRecursive(int key) {
        rootNoRecursion = deleteRec(rootNoRecursion, key);
    }
    
    public Node deleteRec(Node root, int key) {
        if (root == null) {
            // I mean; no
            return root;
        } else {
            if (key < root.getValue()) {
                root.setLeft(deleteRec(root.getLeft(), key));
            } else {
                if (key > root.getValue()) {
                    root.setRight(deleteRec(root.getRight(), key));
                } else {
                    if (root.getLeft() == null) {
                        return root.getRight();
                    } else {
                        if (root.getRight() == null) {
                            return root.getLeft();
                        }
                    }
                    root.setValue(minValue(root.getRight()));
                    root.setRight(deleteRec(root.getRight(), root.getValue()));
                }
            }
            return root;
        }
    }
    
    public int minValue(Node root) {
        int minV = root.getValue();
        while (root.getLeft() != null) {
            minV = root.getValue();
            root = root.getLeft();
        }
        return minV;
    }
    
    public void add(int toadd) {
        addWithoutRecursion(toadd);
       // addWithRecursion(toadd, recursiveRoot);
    }
    
    /* Broken, might fix later
    
    public void addWithRecursion(int toadd,Node root) {
        Node toinsert = new Node(toadd);
        if (root == null) {
            root = toinsert;
        } else if (root.getValue() > toinsert.getValue()) {
            // Go left
            if (root.getLeft() == null) {
                root.setLeft(toinsert);
            } else {
                //root = root.getLeft();
                addWithRecursion(toadd, root.getLeft());
            }
        } else if (root.getValue() < toinsert.getValue()) {
            // Go right
            if (root.getRight() == null) {
                root.setRight(toinsert);
            } else {
                //root = root.getRight();
                addWithRecursion(toadd, root.getRight());
            }
        } else {
            // Don't do anything
            System.err.println(toinsert.getValue()+" <> "+root.getValue());
        } 
    }*/
    
    public void addWithoutRecursion(int toadd) {
        Node toinsert = new Node(toadd);
        if (rootNoRecursion == null) {
            rootNoRecursion = toinsert;
        } else {
            // Start going down the tree
            Node currentNode = rootNoRecursion;
            // Used to track if we find a place to insert at or not
            boolean foundLeaf = false;
            while (!foundLeaf){
                // check if we need to go right or left
                if (currentNode.getValue() > toinsert.getValue()) {
                    // Go left
                    // If we can insert, do so, otherwise move down and try again
                    if (currentNode.getLeft() == null) {
                        currentNode.setLeft(toinsert);
                        foundLeaf = true;
                    } else {
                        currentNode = currentNode.getLeft();
                    }
                } else if (currentNode.getValue() < toinsert.getValue()){
                    // Go right
                    // If we can insert, do so, otherwise move down and try again
                    if (currentNode.getRight() == null) {
                        currentNode.setRight(toinsert);
                        foundLeaf = true;
                    } else {
                        currentNode = currentNode.getRight();
                    }
                } else {
                    // Nothing done if equivalent found
                }
            }
        } 
    }
    
       public void postOrderNotMine() {
        //String out = "";
        postOrderNotMine(rootNoRecursion);
        //return out;
    }
    
    public void postOrderNotMine(Node n) {
        if (n != null) {
            postOrderNotMine(n.getLeft());
            postOrderNotMine(n.getRight());
            System.out.println(n.getValue());
        }
    }   
    
      public void preOrderNotMine() {
        //String out = "";
        preOrderNotMine(rootNoRecursion);
        //return out;
    }
    
    public void preOrderNotMine(Node n) {
        if (n != null) {
            System.out.println(n.getValue());
            preOrderNotMine(n.getLeft());
            preOrderNotMine(n.getRight());
        }
    }
    
    public void inOrderNotMine() {
        //String out = "";
        inOrderNotMine(rootNoRecursion);
        //return out;
    }
    
    public void inOrderNotMine(Node n) {
        if (n != null) {
            inOrderNotMine(n.getLeft());
            System.out.println(n.getValue());
            inOrderNotMine(n.getRight());
        }
    }

    public Node search(int key) {
        Node newKey = new Node(key);
        boolean foundLeaf = false;
        boolean foundIt = false;
        Node cursor = rootNoRecursion;
        while (!foundLeaf) {
            if (newKey.getValue() == cursor.getValue()) {
                foundIt = true;
                foundLeaf = true;
            } else {
                if (newKey.getValue() > cursor.getValue()) {
                    // Go right
                    if (cursor.getRight() == null) {
                        foundLeaf = true;
                    } else {
                        cursor = cursor.getRight();
                    }
                }
                if (newKey.getValue() < cursor.getValue()) {
                    // Go Left
                    if (cursor.getLeft() == null) {
                        foundLeaf = true;
                    } else {
                        cursor = cursor.getLeft();
                    }
                }
            }
        }
        
        if (foundIt) {
            return cursor;
        } else {
            return null;
        }
    }
    
    /* Broken, might fix later
    
    public String inOrder() {
        return inOrder(rootNoRecursion);
    }
    
    public String inOrder(Node root){
        // Check if null
        if (root == null) {
            return "";
        }
        String out = "";
        // Go left as far as possible
        if (root.getLeft() != null) {
            inOrder(root.getLeft());
            if (root.getRight() != null) {
                inOrder(root.getRight());
            }
        } else {
            out = out+root.getValue()+" ";
        }
        return out;
    }*/
}